1、爬楼梯
思想：也就是斐波拉契问题，为了避免 每次递归都要计算所有的数，可以建个数组，将所有数放到对应的下标中即可
class Solution {
public:
    int climbStairs(int n) {
        if(n<=2)
            return n;
        int a[65536]={0};
        a[1]=1;
        a[2]=2;
        for(int i=3;i<=n;i++)
        {
            a[i]=a[i-1]+a[i-2];
        }
        return a[n-1]+a[n-2];
    }
};

2、有个数组，里面的数在1-n的范围里，但是有的数出现2次，有的缺失，找到缺失的数（不能额外创建空间，时间复杂度为0(n)）
思想：因为时间复杂度 以及不能创建额外的空间，这2点要求叫恶心
所以，只能在原数组中操作，于是想到了  遍历每个数，然后将对应的下标里面的数改为负数，这样在遍历一次数组，是正数的下标也就是消失的数
class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        vector<int> v;
        for(int i=0;i<nums.size();i++)
        {
            nums[abs(nums[i])-1]=-abs(nums[abs(nums[i])-1]);
        }
        for(int i=0;i<nums.size();++i)
        {
            if(nums[i]>0)
            {
                v.push_back(i+1);
            }
        }
        return v;
    }
};

3、二叉树中为某个和的路径
思想：递归加回溯
前序遍历，因为每次访问的都是根，这样就可以递归到最左，但是得回溯，也就是递归回来后，得将最后一个元素放出来，因为有新的元素进去
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> vv;
    vector<int> v;
    void dfs(TreeNode* root, int target)
    {
        if(root==nullptr)
            return;
        target-=root->val;
        v.push_back(root->val);
        if(target==0&&root->left==nullptr&&root->right==nullptr)
        {
            vv.push_back(v);
        }
        else
        {
            dfs(root->left,target);
            dfs(root->right,target);
        }
       //回溯
        v.pop_back();
    }
    vector<vector<int>> pathSum(TreeNode* root, int target) {
        dfs(root,target);
        return vv;
    }
};